题目分析

本题很有趣，如果想得到很简单，如果想不到就会很难，提示小伙伴们能否从两个数开始思考呢？

排序

看第一个例子[10, 2]会组成210，在本题中，因为字符串”210”大于“102”，所以将“2”放在前面，我们自定义排序方式，在Java中使用字符串的CompareTo方法，可以比较”ab”和”ba”的大小。

如果排序的对象间能够满足传递性的规律，则排序方式一定是正确的。什么是传递性呢？如果$ab \le ba$，$bc \le cb$，能够推导出来$ac \le ca$则说明自定义的排序方式是正确的。

$$a x pow(10, len(b)) + b \le b x pow(10, len(a)) + a$$ 可得
$$a x (pow(10, len(b) - 1) \le b x (pow(10, len(a) - 1)$$
$$b x pow(10, len(c)) + c \le c x pow(10, len(b)) + b$$ 可得
$$b x (pow(10, len(c) - 1) \le c x (pow(10, len(b) - 1)$$
两边相乘可得
$$a x b x (pow(10, len(b) - 1) x pow(10, len(c) - 1) \le b x c x pow(10, len(a) - 1) x pow(10, len(b) - 1)$$
当$b = 0$时，必然满足条件
当$b \ne 0$时，两边同时除以$b x pow(10, len(b) - 1)$，可得
$$a x pow(10, len(c) - 1) \le c x pow(len(a) - 1)$$，化简可得
$$a x pow(10, len(c)) + c \le c x pow(10, len(a)) + a$$ 即
$$ac \le ca$$

算法的时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$

下面是Java语言的题解

class Solution {
    public String largestNumber(int[] nums) {
        int length = nums.length;
        String[] str = new String[length];
        for (int i = 0; i < length; i++) {
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(str, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        if (str[0].equals("0")) {
            return "0";
        }
        StringBuilder res = new StringBuilder();
        for (String tmp : str) {
            res.append(tmp);
        }
        return res.toString();
    }
}

因为本题数据以int形式给出，要先转换为字符串，然后对字符串进行排序，最后再通过StringBuilder的append方法将字符串组合起来，因此代码量非常的长。我们可以采用Java流的特点进行编写代码，有关流的特性，后面有时间我会出一期博客给大家进行讲解，这里先给出代码吧。

class Solution {
    public String largestNumber(int[] nums) {
        return Arrays.stream(nums).allMatch(n -> n == 0) ? "0" : Arrays.stream(nums).mapToObj(String::valueOf).sorted((o1, o2) -> (o2 + o1).compareTo(o1 + o2)).collect(Collectors.joining(""));
    }
}

刷题总结

本题难度不大，但是方法难以想到，希望小伙伴们多多刷题，这样可以开阔视野，遇到一些奇怪的题目也能够很快想出方法。